Gennesaret Kharistio Tjusila, Alexander Hoen, Nils-Christian Kempke, Gioni Mexi, Timo Berthold, Ambros Gleixner, Thorsten Koch und Sebastian Pokutta gewannen den Land-Doig-MIP-Wettbewerb 2026, der auf dem Mixed-Integer Programming Workshop 2026 bekannt gegeben wurde. Der Land-Doig-MIP-Wettbewerb findet jährlich zu Ehren von Ailsa H. Land und Alison G. Harcourt (geb. Doig) statt, den Erfinderinnen des Branch-and-Bound-Algorithmus für die gemischt-ganzzahlige Programmierung (englisch Mixed Integer Programming, kurz MIP). Er zielt darauf ab, die Entwicklung neuer praktischer Techniken zur Lösung von MIP-Problemen zu fördern. Das Thema des diesjährigen Land-Doig-MIP-Wettbewerbs lautete „GPU-basierte Primal-Heuristiken für MIP", motiviert durch die wachsende Dynamik bei GPU-basierten Optimierungsmethoden wie PDLP, einem LP-Löser erster Ordnung, der auf primal-dualen Hybrid-Gradientenmethoden basiert.
Der Gewinnerbeitrag des ZIB – CHAP – basiert auf drei Hauptkomponenten: erstens auf der CPU-Seite verschiedene Fix-and-Propagate-Strategien zusammen mit einer CPU-basierten Tabu-Suche und einer Feasibility-Pump; zweitens auf der GPU-Seite ein GPU-nativer Tabu-Search-Algorithmus zusammen mit LP-Lösung in niedriger Präzision mittels cuPDLPx; und drittens ein Koordinationsmechanismus für die verschiedenen Heuristiken, der über einen gemeinsamen Lösungspool mit hochwertigen zulässigen und partiellen Lösungen implementiert ist.
Bei den 50 für den Wettbewerb bereitgestellten Testinstanzen lieferte die ZIB-Einreichung für 47 Instanzen zulässige Lösungen und lag damit vor Gurobi im Standardmodus (44) und NVIDIA cuOpt im reinen Heuristik-Modus (43). Auf demselben Instanzen-Set demonstrierte das Team zudem, dass ein kombinierter CPU–GPU-Ansatz einen reinen CPU-Ansatz sowohl beim Gap (8,84 % gegenüber 19,57 %) als auch beim Primalintegral (41,84 gegenüber 72,59) übertrifft.
Das Foto zeigt von links nach rechts: Christian Tjandraatmadja, Softwareentwickler im Operations-Research-Team von Google Research, und Gioni Mexi, der die Auszeichnung im Namen des Teams entgegennahm.
